package base.C06_BinarySearch;

/**
 * Instruction：找到==某个数的第一个 vs 找到>=某个数的第一个
 * 算法: 找到==某个数的第一个 - 二分找到, 继续前看 / 没有找到, 返回-1
 * 算法: 找到>=某个数的第一个 - 二分找到, 继续前看 / 没有找到, 返回无越界前提下的middle+1
 * Author：@author MaLi
 */
public class Code05_FindTheFirstPlus {
    public static int find(int[] arr, int num) {
        //有效性验证
        if (arr == null || arr.length < 1)
            return -1;
        //查找第一个给定值
        int start = 0;
        int end = arr.length - 1;
        int middle = 0;
        while (start <= end) {
            middle = start + ((end - start) >> 1);
            if (arr[middle] == num) {
                if ((middle - 1) >= 0 && arr[middle - 1] == num) {
                    end = middle - 1; //说明当前middle值还不是end, end至少是middle-1(数组不越界的前提下)
                } else {
                    return middle;
                }
            } else if (arr[middle] > num) { //说明中间值在目标值的右边, 我们应该重新确定end值, 排除一半无用值
                end = middle - 1;
            } else {
                start = middle + 1;  //说明中间值在目标值的左边, 我们应该重新确定start值, 排除一半无用值
            }
        }
        //以上没有找到指定值, 那么判断middle值与目标值大小
        //1 1 1 1 3 3 3 3
        if (arr[middle] > num)
            //middle值比num值大
            return middle;
        else
            //middle值比num值小, 那么就在不越界的前提下, 返回下一个
            return middle + 1 > arr.length - 1 ? -1 : middle + 1;
    }
}
